/*
 * @Author: Jiraiya
 * @Date: 2020-06-12 15:50:04
 * @LastEditors: Jiraiya
 * @LastEditTime: 2020-06-12 15:50:55
 * @Description: 
 */ 
class TreeNode{
    constructor(val){
        this.val = val;
        this.left = this.right = null;
    }
}

// 搜索二叉树的中序遍历序列是有序的
class SearchTree{
    constructor(){
        this.root = null;
    }

    // 插入节点
    insert(val){
        if(this.root === null){
            this.root = new TreeNode(val);
        }else{
            this.insertNode(this.root, val);
        }
    }

    insertNode(node, val){
        if(node.val > val){
            if(!node.left){
                node.left = new TreeNode(val);
            }else{
                this.insertNode(node.left, val);
            }
        }else{
            if(!node.right){
                node.right = new TreeNode(val);
            }else{
                this.insertNode(node.rigth, val);
            }
        }
    }

    // 获取最大的节点
    maxNode(node){
        while(node !== null && node.right !== null){
            node = node.right;
        }
        return node;
    }

    // 获取最小的节点
    minNode(node){
        while(node !==null && node.left !== null){
            node = node.left;
        }
        return node;
    }

    //搜索某个val是否存在
    search(val){
        return this.searchNode(this.root, val);
    }

    searchNode(root, val){
        if(root === null) return false;
        if(root.val < val){
            return this.searchNode(root.right, val);
        }else if(root.val > val){
            return this.searchNode(root.left, val);
        }else{
            return true;
        }
    }

    //移除一个节点
    remove(val){
        this.root = this.removeSearch(this.root, val);
    }

    removeSearch(node, val){
        if(node === null) return null;
        if(node.val < val){
            node.right = this.removeSearch(node.right, val);
            return node;
        }else if(node.val > val){
            node.left = this.removeSearch(node.left, val);
            return node;
        }else{
            if(node.left === null && node.right === null){
                node = null;
                return node;
            }
            if(node.left === null){
                node = node.right;
                return node;
            }

            if(node.rigth === null){
                node = node.left;
                return node;
            }

            //左右子节点都存在
            const aux = this.minNode(node.right);
            node.val = aux.val;
            node.right = this.removeSearch(node.right, aux.val);
            return node;
        }
    }

}

module.exports = SearchTree;